home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / scheme / schmrprt / r4rs.lha / syn.tex (.txt) < prev   
Encoding:
LaTeX Document  |  1991-11-08  |  11.1 KB  |  248 lines
  1. \chapter{Formal syntax and semantics}
  2. \label{formalchapter}
  3. This chapter provides formal descriptions of what has already been
  4. described informally in previous chapters of this report.
  5. \todo{Allow grammar to say that else clause needn't be last?}
  6. \section{Formal syntax}
  7. \label{BNF}
  8. This section provides a formal syntax for Scheme written in an extended
  9. BNF.  The syntax for the entire language, including features which are
  10. not essential, is given here.
  11. All spaces in the grammar are for legibility.  Case is insignificant;
  12. for example, {\cf \#x1A} and {\cf \#X1a} are equivalent.  \meta{empty}
  13. stands for the empty string.
  14. The following extensions to BNF are used to make the description more
  15. concise:  \arbno{\meta{thing}} means zero or more occurrences of
  16. \meta{thing}; and \atleastone{\meta{thing}} means at least one
  17. \meta{thing}.
  18. \subsection{Lexical structure}
  19. This section describes how individual tokens\index{token} (identifiers,
  20. numbers, etc.) are formed from sequences of characters.  The following
  21. sections describe how expressions and programs are formed from sequences
  22. of tokens.
  23. \meta{Intertoken space} may occur on either side of any token, but not
  24. within a token.
  25. \vest Tokens which require implicit termination (identifiers, numbers,
  26. characters, and dot) may be terminated by any \meta{delimiter}, but not
  27. necessarily by anything else.
  28. \begin{grammar}%
  29. \meta{token} \: \meta{identifier} \| \meta{boolean} \| \meta{number}\index{identifier}
  30. \>  \| \meta{character} \| \meta{string}
  31. \>  \| ( \| ) \| \sharpsign( \| \singlequote{} \| \backquote{} \| , \| ,@ \| {\bf.}
  32. \meta{delimiter} \: \meta{whitespace} \| ( \| ) \| " \| ;
  33. \meta{whitespace} \: \meta{space or newline}
  34. \meta{comment} \: ; \= $\langle$\rm all subsequent characters up to a
  35.             \>\ \rm line break$\rangle$\index{comment}
  36. \meta{atmosphere} \: \meta{whitespace} \| \meta{comment}
  37. \meta{intertoken space} \: \arbno{\meta{atmosphere}}%
  38. \end{grammar}
  39. \label{extendedalphas}
  40. \label{identifiersyntax}
  41. % This is a kludge, but \multicolumn doesn't work in tabbing environments.
  42. \setbox0\hbox{\cf\meta{variable} \goesto{} $\langle$}
  43. \begin{grammar}%
  44. \meta{identifier} \: \meta{initial} \arbno{\meta{subsequent}}
  45.  \>  \| \meta{peculiar identifier}
  46. \meta{initial} \: \meta{letter} \| \meta{special initial}
  47. \meta{letter} \: a \| b \| c \| ... \| z
  48. \meta{special initial} \: ! \| \$ \| \% \| \verb"&" \| * \| / \| : \| < \| =
  49.  \>  \| > \| ? \| \verb"~" \| \verb"_" \| \verb"^"
  50. \meta{subsequent} \: \meta{initial} \| \meta{digit}
  51.  \>  \| \meta{special subsequent}
  52. \meta{digit} \: 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9
  53. \meta{special subsequent} \: .\ \| + \| -
  54. \meta{peculiar identifier} \: + \| - \| ...
  55. %\| 1+ \| -1+
  56. \meta{syntactic keyword} \: \meta{expression keyword}\index{keyword}\index{syntactic keyword}
  57.  \>  \| else \| => \| define 
  58.  \>  \| unquote \| unquote-splicing
  59. \meta{expression keyword} \: quote \| lambda \| if
  60.  \>  \| set! \| begin \| cond \| and \| or \| case
  61.  \>  \| let \| let* \| letrec \| do \| delay
  62.  \>  \| quasiquote
  63. \copy0\rm any \meta{identifier} that isn't\index{variable}
  64. \hbox to 1\wd0{\hfill}\ \rm also a \meta{syntactic keyword}$\rangle$
  65. \meta{boolean} \: \schtrue{} \| \schfalse{}
  66. \meta{character} \: \#\backwhack{} \meta{any character}
  67.  \>  \| \#\backwhack{} \meta{character name}
  68. \meta{character name} \: space \| newline
  69. \todo{Explain what happens in the ambiguous case.}
  70. \meta{string} \: " \arbno{\meta{string element}} "
  71. \meta{string element} \: \meta{any character other than \doublequote{} or \backwhack}
  72.  \>  \| \backwhack\doublequote{} \| \backwhack\backwhack %
  73. \end{grammar}
  74. \label{numbersyntax}
  75. \begin{grammar}%
  76. \meta{number} \: \meta{num $2$}%
  77.        \| \meta{num $8$}
  78.    \>  \| \meta{num $10$}%
  79.        \| \meta{num $16$}
  80. \end{grammar}
  81. The following rules for \meta{num $R$}, \meta{complex $R$}, \meta{real
  82. $R$}, \meta{ureal $R$}, \meta{uinteger $R$}, and \meta{prefix $R$}
  83. should be replicated for \hbox{$R = 2, 8, 10,$}
  84. and $16$.  There are no rules for \meta{decimal $2$}, \meta{decimal
  85. $8$}, and \meta{decimal $16$}, which means that numbers containing
  86. decimal points or exponents must be in decimal radix.
  87. \todo{Mark Meyer and David Bartley want to fix this.  (What? -- Will)}
  88. \begin{grammar}%
  89. \meta{num $R$} \: \meta{prefix $R$} \meta{complex $R$}
  90. \meta{complex $R$} \: %
  91.          \meta{real $R$} %
  92.       \| \meta{real $R$} @ \meta{real $R$}
  93.    \> \| \meta{real $R$} + \meta{ureal $R$} i %
  94.       \| \meta{real $R$} - \meta{ureal $R$} i
  95.    \> \| \meta{real $R$} + i %
  96.       \| \meta{real $R$} - i
  97.    \> \| + \meta{ureal $R$} i %
  98.       \| - \meta{ureal $R$} i %
  99.       \| + i %
  100.       \| - i
  101. \meta{real $R$} \: \meta{sign} \meta{ureal $R$}
  102. \meta{ureal $R$} \: %
  103.          \meta{uinteger $R$}
  104.    \> \| \meta{uinteger $R$} / \meta{uinteger $R$}
  105.    \> \| \meta{decimal $R$}
  106. \meta{decimal $10$} \: %
  107.          \meta{uinteger $10$} \meta{suffix}
  108.    \> \| . \atleastone{\meta{digit $10$}} \arbno{\#} \meta{suffix}
  109.    \> \| \atleastone{\meta{digit $10$}} . \arbno{\meta{digit $10$}} \arbno{\#} \meta{suffix}
  110.    \> \| \atleastone{\meta{digit $10$}} \atleastone{\#} . \arbno{\#} \meta{suffix}
  111. \meta{uinteger $R$} \: \atleastone{\meta{digit $R$}} \arbno{\#}
  112. \meta{prefix $R$} \: %
  113.          \meta{radix $R$} \meta{exactness}
  114.    \> \| \meta{exactness} \meta{radix $R$}
  115. \end{grammar}
  116. \begin{grammar}%
  117. \meta{suffix} \: \meta{empty} 
  118.    \> \| \meta{exponent marker} \meta{sign} \atleastone{\meta{digit $10$}}
  119. \meta{exponent marker} \: e \| s \| f \| d \| l
  120. \meta{sign} \: \meta{empty}  \| + \|  -
  121. \meta{exactness} \: \meta{empty} \| \#i\sharpindex{i} \| \#e\sharpindex{e}
  122. \meta{radix 2} \: \#b\sharpindex{b}
  123. \meta{radix 8} \: \#o\sharpindex{o}
  124. \meta{radix 10} \: \meta{empty} \| \#d
  125. \meta{radix 16} \: \#x\sharpindex{x}
  126. \meta{digit 2} \: 0 \| 1
  127. \meta{digit 8} \: 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7
  128. \meta{digit 10} \: \meta{digit}
  129. \meta{digit 16} \: \meta{digit $10$} \| a \| b \| c \| d \| e \| f %
  130. \end{grammar}
  131. \todo{Mark Meyer of TI sez, shouldn't we allow {\tt 1e3/2}?}
  132. \subsection{External representations}
  133. \label{datumsyntax}
  134. \meta{Datum} is what the \ide{read} procedure (section~\ref{read})
  135. successfully parses.  Note that any string that parses as an
  136. \meta{ex\-pres\-sion} will also parse as a \meta{datum}.  \label{datum}
  137. \begin{grammar}%
  138. \meta{datum} \: \meta{simple datum} \| \meta{compound datum}
  139. \meta{simple datum} \: \meta{boolean} \| \meta{number}
  140. \>  \| \meta{character} \| \meta{string} \|  \meta{symbol}
  141. \meta{symbol} \: \meta{identifier}
  142. \meta{compound datum} \: \meta{list} \| \meta{vector}
  143. \meta{list} \: (\arbno{\meta{datum}}) \| (\atleastone{\meta{datum}} .\ \meta{datum})
  144. \>    \| \meta{abbreviation}
  145. \meta{abbreviation} \: \meta{abbrev prefix} \meta{datum}
  146. \meta{abbrev prefix} \: ' \| ` \| , \| ,@
  147. \meta{vector} \: \#(\arbno{\meta{datum}}) %
  148. \end{grammar}
  149. \subsection{Expressions}
  150. \begin{grammar}%
  151. \meta{expression} \: \meta{variable}
  152. \>  \| \meta{literal}
  153. \>  \| \meta{procedure call}
  154. \>  \| \meta{lambda expression}
  155. \>  \| \meta{conditional}
  156. \>  \| \meta{assignment}
  157. \>  \| \meta{derived expression}
  158. \meta{literal} \: \meta{quotation} \| \meta{self-evaluating}
  159. \meta{self-evaluating} \: \meta{boolean} \| \meta{number}
  160. \>  \| \meta{character} \| \meta{string}
  161. \meta{quotation} \: '\meta{datum} \| (quote \meta{datum})
  162. \meta{procedure call} \: (\meta{operator} \arbno{\meta{operand}})
  163. \meta{operator} \: \meta{expression}
  164. \meta{operand} \: \meta{expression}
  165. \meta{lambda expression} \: (lambda \meta{formals} \meta{body})
  166. \meta{formals} \: (\arbno{\meta{variable}}) \| \meta{variable}
  167. \>  \| (\atleastone{\meta{variable}} .\ \meta{variable})
  168. \meta{body} \: \arbno{\meta{definition}} \meta{sequence}
  169. \meta{sequence} \: \arbno{\meta{command}} \meta{expression}
  170. \meta{command} \: \meta{expression}
  171. \meta{conditional} \: (if \meta{test} \meta{consequent} \meta{alternate})
  172. \meta{test} \: \meta{expression}
  173. \meta{consequent} \: \meta{expression}
  174. \meta{alternate} \: \meta{expression} \| \meta{empty}
  175. \meta{assignment} \: (set! \meta{variable} \meta{expression})
  176. \meta{derived expression} \:
  177. \>  \> (cond \atleastone{\meta{cond clause}})
  178. \>  \| (cond \arbno{\meta{cond clause}} (else \meta{sequence}))
  179. \>  \| (c\=ase \meta{expression}
  180. \>       \>\atleastone{\meta{case clause}})
  181. \>  \| (c\=ase \meta{expression}
  182. \>       \>\arbno{\meta{case clause}}
  183. \>       \>(else \meta{sequence}))
  184. \>  \| (and \arbno{\meta{test}})
  185. \>  \| (or \arbno{\meta{test}})
  186. \>  \| (let (\arbno{\meta{binding spec}}) \meta{body})
  187. \>  \| (let \meta{variable} (\arbno{\meta{binding spec}}) \meta{body})
  188. \>  \| (let* (\arbno{\meta{binding spec}}) \meta{body})
  189. \>  \| (letrec (\arbno{\meta{binding spec}}) \meta{body})
  190. \>  \| (begin \meta{sequence})
  191. \>  \| (d\=o \=(\arbno{\meta{iteration spec}})
  192. \>       \>  \>(\meta{test} \meta{sequence})
  193. \>       \>\arbno{\meta{command}})
  194. \>  \| (delay \meta{expression})
  195. \>  \| \meta{quasiquotation}
  196. \meta{cond clause} \: (\meta{test} \meta{sequence})
  197. \>   \| (\meta{test})
  198. \>   \| (\meta{test} => \meta{recipient})
  199. \meta{recipient} \: \meta{expression}
  200. \meta{case clause} \: ((\arbno{\meta{datum}}) \meta{sequence})
  201. \meta{binding spec} \: (\meta{variable} \meta{expression})
  202. \meta{iteration spec} \: (\meta{variable} \meta{init} \meta{step})
  203. \> \| (\meta{variable} \meta{init})
  204. \meta{init} \: \meta{expression}
  205. \meta{step} \: \meta{expression} %
  206. \end{grammar}
  207. \subsection{Quasiquotations}
  208. The following grammar for quasiquote expressions is not context-free.
  209. It is presented as a recipe for generating an infinite number of
  210. production rules.  Imagine a copy of the following rules for $D = 1, 2,
  211. 3, \ldots$.  $D$ keeps track of the nesting depth.
  212. \begin{grammar}%
  213. \meta{quasiquotation} \: \meta{quasiquotation 1}
  214. \meta{template 0} \: \meta{expression}
  215. \meta{quasiquotation $D$} \: `\meta{template $D$}
  216. \>    \| (quasiquote \meta{template $D$})
  217. \meta{template $D$} \: \meta{simple datum}
  218. \>    \| \meta{list template $D$}
  219. \>    \| \meta{vector template $D$}
  220. \>    \| \meta{unquotation $D$}
  221. \meta{list template $D$} \: (\arbno{\meta{template or splice $D$}})
  222. \>    \| (\atleastone{\meta{template or splice $D$}} .\ \meta{template $D$})
  223. \>    \| '\meta{template $D$}
  224. \>    \| \meta{quasiquotation $D+1$}
  225. \meta{vector template $D$} \: \#(\arbno{\meta{template or splice $D$}})
  226. \meta{unquotation $D$} \: ,\meta{template $D-1$}
  227. \>    \| (unquote \meta{template $D-1$})
  228. \meta{template or splice $D$} \: \meta{template $D$}
  229. \>    \| \meta{splicing unquotation $D$}
  230. \meta{splicing unquotation $D$} \: ,@\meta{template $D-1$}
  231. \>    \| (unquote-splicing \meta{template $D-1$}) %
  232. \end{grammar}
  233. In \meta{quasiquotation}s, a \meta{list template $D$} can sometimes
  234. be confused with either an \meta{un\-quota\-tion $D$} or a \meta{splicing
  235. un\-quo\-ta\-tion $D$}.  The interpretation as an
  236. \meta{un\-quo\-ta\-tion} or \meta{splicing
  237. un\-quo\-ta\-tion $D$} takes precedence.
  238. \subsection{Programs and definitions}
  239. \begin{grammar}%
  240. \meta{program} \: \arbno{\meta{command or definition}}
  241. \meta{command or definition} \: \meta{command} \| \meta{definition}
  242. \meta{definition} \: (define \meta{variable} \meta{expression})
  243. \>   \| (define (\meta{variable} \meta{def formals}) \meta{body})
  244. \>   \| (begin \arbno{\meta{definition}})
  245. \meta{def formals} \: \arbno{\meta{variable}}
  246. \>   \| \atleastone{\meta{variable}} .\ \meta{variable} %
  247. \end{grammar}
  248.